1. Field of the Invention
The present invention relates to a packet switching device for packet communication, and, in particular, to a packet switching device which transmits a packet from one communication channel to another communication channel.
2. Description of the Prior Art
In order to transmit data, wide use has been made of a packet communication system in which the data is divided into sections of a certain size, these sections are bundled, and packets to which are affixed the destination address are generated. The communication system then determines the route of the packet by which the packet will be transmitted while making reference to the destination address. It is possible for many more users to utilize the capabilities of a packet communication system at the same time for the communication of useful data only because the destination address is attached to the data. It has the advantage that it is possible to improve the communication efficiency and reduce communication costs.
In order to widen the sphere of use of the package communication system, it is indispensable to construct a hardware packet switching device which can transmit, without the aid of computer program, a number of packets input from an input communication channel to an output communication channel which indicates routing data of these packets, as described in U.S. Pat. No. 4,491,945. One commonly known method of realizing this packet switching device comprises a means wherein a switch is provided which can accommodate a plurality of both input and output communication channels; in each input communication channel a buffer temporarily stores a packet from an input communication channel corresponding to that input communication channel; the switch analyses the route data for the lead packet from the oldest among the packets which are stored in the buffers provided in each input communication channel and determines the output communication channel for transmitting the packet; and a means for transmitting the lead packet to the intended output communication channel.
FIG. 1(A) is a block diagram showing this type of a conventional packet switching device.
This diagram shows a switch 10 which transmits an input packet to an, output communication channel which indicates the routing data which the packet contains; a plurality of input communication channels 12a, 12b, 12c . . . 12n which input the packet to a buffer; a plurality of buffers 11a, 11b . . . 11n provided to correspond to the above input communication channels; and a plurality of output communication channels 13a, 13b, . . . 13n which output the packets from the switch.
In the conventional system shown in FIG. 1(A), the switch analyses the routing data for the head packet in each buffer, and transmits the packet in an output communication channel which shows the channel data from a certain input communication channel.
However, with this method, in the case where the head packets of a plurality of buffers are supposed to be output in the same output communication channel, specifically, in the case where packet collisions occur, one of those packets is selected and the remaining packets are not transmitted from the buffers. For this reason, packet collisions is a cause of reduction of the throughput of the buffers, and in addition causes a decrease in the throughput of the packet switching device. Here, throughput is defined as the ratio of the actual number of packets transmitted in a certain time interval to the maximum number of packets which can be transmitted in that time interval.
In the case where the output communication channel facing a packet positioned on the input communication channel is randomly determined, when using the conventional technology described above, the throughput of a 2.times.2 packet switching device which accomodates two input communication channels and two output communication channels is a maximum of 0.75 for one output communication channel, according to such references as "IEEE transactions on Computers" volume C-30, No. 4, pages 273 to 282, April 1981 by D. M. Dias and J. M. Jump "Analysis and Simulation of Buffered Delta Network." For an input communication channel, when offered load is greater than the throughput of the output communication channel buffer overflows occurs, and the number of discarded packets increase. Packet discard has a bad influence on data communication so that with packet switching devices using existing technology there is the drawback that offered loads cannot be high to the number of communication channels. In the abovementioned 2.times.2 packet switching device, when offered load becomes 0.75 or greater on that input communication channel, the number of discarded packets is increased and it is impossible to maintain adequate characteristics as a packet switching device. Here, load is defined as the ratio of the actual number of packets inputted in a given time interval to the maximum number of packets which can be input in that time interval.
As outlined above, because considerable packet discard is occured as a result of the inadequacy of the throughput of a buffer attributable to packet collision, the drawback occurs in which the conventional packet switching system or device cannot be used in the status in which a offered load is high to the number of communication channel.